package 回溯;


import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

//https://leetcode.cn/problems/flood-fill/
public class 图像渲染 {
    // fun_DFS_2、funBFS辅助处理
    int[] x = new int[]{-1 , 0 , 0 , 1};
    int[] y = new int[]{0 , -1 , 1 , 0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        /*
        if (image[sr][sc] != color)
        //这个是防止特殊情况的，按理不该这样，但是会栈溢出
            fun_DFS(image , sr , sc , image[sr][sc] , color);
        return image;
         */
        /*
        if (image[sr][sc] != color){
            //这个是防止特殊情况的，按理不该这样，但是会栈溢出
            return fun_DFS_1(image , sr , sc , color);
        }
        return image;
         */
        if (image[sr][sc] != color){
            //这个是防止特殊情况的，按理不该这样，但是会栈溢出
            fun_BFS(image , sr , sc , color);
        }
        return image;
    }
    public int[][] fun_DFS_1(int[][] image, int sr, int sc, int color) {
        int old = image[sr][sc];
        image[sr][sc] = color;
        if (sr - 1 >= 0 && image[sr - 1][sc] == old){
            fun_DFS_1(image , sr - 1 , sc , color);
        }
        if (sr + 1 < image.length && image[sr + 1][sc] == old){
            fun_DFS_1(image , sr + 1 , sc , color);
        }
        if (sc - 1 >= 0 && image[sr][sc - 1] == old){
            fun_DFS_1(image , sr , sc - 1 , color);
        }
        if (sc + 1 < image[sr].length && image[sr][sc + 1] == old){
            fun_DFS_1(image , sr , sc + 1 , color);
        }
        return image;
    }

    public void fun_DFS_2(int[][] image, int sr, int sc, int old , int color) {
        if (image[sr][sc] == old){
            image[sr][sc] = color;
            for (int i = 0 ; i < 4 ; i++){
                int srx = sr + x[i];
                int scy = sc + y[i];
                if (srx >= 0 && srx < image.length && scy >= 0 && scy < image[0].length){
                    fun_DFS_2(image , srx , scy , old , color);
                }
            }
        }
    }

    public int[][] fun_BFS(int[][] image, int sr, int sc, int newColor) {
        int old = image[sr][sc];
        if (old == newColor) {
            return image;
        }
        int n = image.length, m = image[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc});
        image[sr][sc] = newColor;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int srx = cell[0], scy = cell[1];
            for (int i = 0; i < 4; i++) {
                int mx = srx + x[i], my = scy + y[i];
                if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == old) {
                    queue.offer(new int[]{mx, my});
                    image[mx][my] = newColor;
                }
            }
        }
        return image;
    }
}
